/******************************************************************************
 cnome: A C++ source "genes" discover. :-)

 See more details at:

   http://www.codeplex.com/cnome

 The original author site is at: http://www.alemosbarbosa.com/

 Copyright (c) 2009-2010 Alexandre Lemos Barbosa.
 Distributed under the MIT License. (See accompanying file LICENSE-MIT.txt 
 or at http://www.codeplex.com/cnome/license)
 ******************************************************************************/

#ifndef MULTIVECTOR_H
#define MULTIVECTOR_H

#include <functional>
#include <map>
#include <utility>
#include <vector>
//#include <xutility>

#include <boost/iterator/iterator_adaptor.hpp>
#include <boost/iterator/reverse_iterator.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/utility/enable_if.hpp>

namespace cnome { namespace infra {
template<typename T>
class vectorX: public std::vector<T> {
public:
    typedef std::vector<T> Base;

    vectorX() : Base() {}
    vectorX(const vectorX& x) : Base(x) {}
    vectorX(const Base& p): Base(p) {}

    vectorX new_vectorX(T newItem) const {
        vectorX ret(*this);
        ret.push_back(newItem);

        return ret;
    }

    int get_level() const {return static_cast<int>(this->size()) - 1; }

    bool operator<(const vectorX& rhs) const {
        std::size_t i;
        for (i = 0; i < this->size() && i < rhs.size() && (*this)[i] == rhs[i]; i++);
        if (i >= this->size())
            return i < rhs.size();
        else if (i < rhs.size())
            return (*this)[i] < rhs[i];
        else
            return false;
    }

    bool operator==(const vectorX& rhs) const {
        if (this->size() != rhs.size())
            return false;

        std::size_t i;
        for (i = 0; i < this->size() && (*this)[i] == rhs[i]; i++);

        return i == this->size();
    }

    bool operator!=(const vectorX& other) const {
        return !(*this == other);
    }

    bool operator>(const vectorX& other) const {
        return !(*this < other) && !(*this == other);
    }
};

typedef vectorX<int> MultiVector_PositionT;

// Forwards
template<typename T> 
    class multivector;
template<typename T> 
    class multivector_const_reverse_it;
template<typename T> 
    class multivector_reverse_it;
template<typename T> 
    class multivector_level_const_it;
template<typename T> 
    class multivector_level_const_reverse_it;

template<typename T> 
class multivector_const_it 
  : public boost::iterator_adaptor<
      multivector_const_it<T>,              // Derived
      typename std::map<MultiVector_PositionT, T>::const_iterator // Base
    >
{
 private:
    struct enabler {};  // a private type avoids misuse

 public:
    typedef
 
	typename boost::iterator_adaptor<
	      multivector_const_it<T>,
              typename std::map<MultiVector_PositionT, T>::const_iterator
        >::base_type Base;
    typedef Base BaseAll;
    
    multivector_const_it()
      : multivector_const_it::iterator_adaptor_(), m_mp(new MultiVector_PositionT()), m_mv(0) {}

    explicit multivector_const_it(Base const& p)
      : multivector_const_it::iterator_adaptor_(p), m_mp(new MultiVector_PositionT()), m_mv(0) {}

    template <typename OtherValue>
    multivector_const_it(
        multivector_const_it<OtherValue> const& other
      , typename boost::enable_if<
            boost::is_convertible<OtherValue,Base>
          , enabler
        >::type = enabler()
    )
      : multivector_const_it::iterator_adaptor_(other.base()), m_mp(other.m_mp), m_mv(other.m_mv) {}

    multivector_const_it& operator=(const multivector_const_it& rhs) {
        const_cast<Base&>(this->base()) = rhs.base();
        const_cast<boost::shared_ptr<MultiVector_PositionT>&>(m_mp) = rhs.m_mp;
        m_mv = rhs.m_mv;

        return *this;
    }
protected:
    multivector_const_it(const BaseAll& b, const MultiVector_PositionT& mp, const multivector<T>* mv)
      : multivector_const_it::iterator_adaptor_(b), m_mp(new MultiVector_PositionT(mp)), m_mv(mv) {}
private:
    friend class boost::iterator_core_access;
    friend class multivector<T>;
    friend class multivector_const_reverse_it<T>;
    friend class multivector_reverse_it<T>;
    friend class multivector_level_const_it<T>;
    friend class multivector_level_const_reverse_it<T>;

    void increment();
    void decrement();

    const boost::shared_ptr<MultiVector_PositionT> m_mp;
    const multivector<T>* m_mv;
};

template<typename T> 
class multivector_it : public multivector_const_it<T> {
 private:
    struct enabler {};  // a private type avoids misuse

public:
    typedef multivector_const_it<T> Base;
    typedef typename multivector_const_it<T>::BaseAll BaseAll;

    multivector_it() : Base() {}

    explicit multivector_it(BaseAll const& p) : Base(p) {}

    multivector_it(Base const& p) : Base(p) {}

    template <typename OtherValue>
    multivector_it(
        multivector_it<OtherValue> const& other
      , typename boost::enable_if<
            boost::is_convertible<OtherValue,Base>
          , enabler
        >::type = enabler()
    )
      : multivector_const_it<T>(other) {}
 private:
    friend class multivector<T>;
    friend class multivector_reverse_it<T>;

    multivector_it(const BaseAll& b, const MultiVector_PositionT& mp, const multivector<T>* mv)
        : Base(b, mp, mv) {}
};

template<typename T> 
class multivector_const_reverse_it : public boost::reverse_iterator<multivector_const_it<T> > {
 private:
    struct enabler {};  // a private type avoids misuse

 public:
    typedef boost::reverse_iterator<multivector_const_it<T> > Base;
    typedef typename multivector_const_it<T>::BaseAll BaseAll;

    multivector_const_reverse_it() : Base() {}

    explicit multivector_const_reverse_it(Base const& p) : Base(p) {}

    template <typename OtherValue>
    multivector_const_reverse_it(
        multivector_const_reverse_it<OtherValue> const& other
      , typename boost::enable_if<
            boost::is_convertible<OtherValue,Base>
          , enabler
        >::type = enabler()
    )
      : Base(other) {}

    multivector_const_reverse_it(multivector_const_it<T> other) : Base(++other) {}

    multivector_const_reverse_it(multivector_it<T> other) : Base(++other) {}
 protected:
    multivector_const_reverse_it(const BaseAll& b, const MultiVector_PositionT& mp, const multivector<T>* mv)
        : Base(typename Base::base_type(b, mp, mv)) {}
 private:
    friend class multivector<T>;
};

template<typename T> 
class multivector_reverse_it : public multivector_const_reverse_it<T> {
 private:
    struct enabler {};  // a private type avoids misuse

 public:
    typedef multivector_const_reverse_it<T> Base;
    typedef typename multivector_const_it<T>::BaseAll BaseAll;

    multivector_reverse_it() : Base() {}

    explicit multivector_reverse_it(BaseAll const& p) : Base(p) {}

    multivector_reverse_it(Base const& p) : Base(p) {}

    template <typename OtherValue>
    multivector_reverse_it(
        multivector_reverse_it<OtherValue> const& other
      , typename boost::enable_if<
            boost::is_convertible<OtherValue,Base>
          , enabler
        >::type = enabler()
    )
      : multivector_const_reverse_it<T>(other) {}
 
    multivector_reverse_it(multivector_it<T>& other) : Base(other) {}
private:
    friend class multivector<T>;

    multivector_reverse_it(const BaseAll& b, const MultiVector_PositionT& mp, const multivector<T>* mv)
        : Base(b, mp, mv) {}
};

// TODO (alb): Implement a verification on the * and -> operators to verify if the iterator address is inside
//             the level. It must throw the appropriate exception when this is not the case. The address isn't
//             inside the level when its at the level end position.
// 21sep2010
template<typename T> 
class multivector_level_const_it 
  : public boost::iterator_adaptor<
      multivector_level_const_it<T>,   // Derived
      multivector_const_it<T>          // Base
    >
{
 private:
    struct enabler {};  // a private type avoids misuse

 public:
    typedef
        typename boost::iterator_adaptor<
      	        multivector_level_const_it<T>,
                multivector_const_it<T>
            >::base_type Base;
    typedef typename multivector_const_it<T>::BaseAll BaseAll;

    multivector_level_const_it()
      : multivector_level_const_it::iterator_adaptor_(), m_level(0)  {}

    multivector_level_const_it(int level)
      : multivector_level_const_it::iterator_adaptor_(), m_level(level)  {}

    explicit multivector_level_const_it(Base const& p)
      : multivector_level_const_it::iterator_adaptor_(p), m_level(0)  {}

    template <typename OtherValue>
    multivector_level_const_it(
        multivector_level_const_it<OtherValue> const& other
      , typename boost::enable_if<
            boost::is_convertible<OtherValue,Base>
          , enabler
        >::type = enabler()
    )
      : multivector_level_const_it::iterator_adaptor_(other.base()), m_level(other.m_level){}

 protected:
    multivector_level_const_it(const BaseAll& b, const MultiVector_PositionT& mp, const multivector<T>* mv, int level)
        : multivector_level_const_it::iterator_adaptor_(Base(b, mp, mv)), m_level(level)  {}

    int my_level() const { return static_cast<int>((*this)->first.size()) - 1; }
 private:
    friend class boost::iterator_core_access;
    friend class multivector<T>;
    friend class multivector_level_const_reverse_it<T>;

    void increment();
    void decrement();

    template <class OtherIterator>
    typename Base::super_t::difference_type
    distance_to(OtherIterator const& y) const {
        typename Base::super_t::difference_type sz(0);
        bool isYAtEnd = y.base() == y.base().m_mv->end();
        bool isThisAtEnd = this->base() == this->base().m_mv->end();
        if (isYAtEnd && isThisAtEnd) {
            return sz;
        }
        bool advance;
        if (isYAtEnd) {
            advance = true;
        }
        else if (isThisAtEnd) {
            advance = false;
        }
        else if (y->first == (*this)->first){
            return sz;
        }
        else {
            advance = y->first > (*this)->first;
        }
        if (advance) {
            for (OtherIterator it = *this; it != y; ++it, ++sz);
        } 
        else {
            for (OtherIterator it = y; it != *this; ++it, --sz);
        }
        
        return sz;
    }

    int m_level;
};

template<typename T> 
class multivector_level_it : public multivector_level_const_it<T> {
 private:
    struct enabler {};  // a private type avoids misuse

public:
    typedef multivector_level_const_it<T> Base;
    typedef typename multivector_const_it<T>::BaseAll BaseAll;

    multivector_level_it() : Base() {}

    multivector_level_it(int level) : Base(level) {}

    explicit multivector_level_it(BaseAll const& p) : Base(p) {}

    multivector_level_it(Base const& p) : Base(p) {}

    template <typename OtherValue>
    multivector_level_it(
        multivector_level_it<OtherValue> const& other
      , typename boost::enable_if<
            boost::is_convertible<OtherValue,Base>
          , enabler
        >::type = enabler()
    )
      : multivector_level_it(other) {}
 private:
    friend class multivector<T>;

    multivector_level_it(const BaseAll& b, const MultiVector_PositionT& mp, const multivector<T>* mv, int level)
        : Base(b, mp, mv, level) {}
};

template<typename T> 
class multivector_level_const_reverse_it 
  : public boost::iterator_adaptor<
      multivector_level_const_reverse_it<T>,  // Derived
      multivector_level_const_it<T>           // Base
  > 
{
 private:
    struct enabler {};  // a private type avoids misuse

 public:
    typedef multivector_level_const_it<T> Base;
    typedef typename multivector_const_it<T>::BaseAll BaseAll;

    multivector_level_const_reverse_it() : Base() {}

    multivector_level_const_reverse_it(int level) : Base(level) {}

    multivector_level_const_reverse_it(Base const& b) : Base(b) {}

    explicit multivector_level_const_reverse_it(BaseAll const& p) : Base(p) {}

    template <typename OtherValue>
    multivector_level_const_reverse_it(
        multivector_level_const_reverse_it<OtherValue> const& other
      , typename boost::enable_if<
            boost::is_convertible<OtherValue,Base>
          , enabler
        >::type = enabler()
    )
       :  boost::iterator_adaptor<
             multivector_level_const_reverse_it<T>,
             multivector_level_const_it<T>
          >::iterator_adaptor_(other) {}

    multivector_level_const_reverse_it(multivector_level_const_it<T> other) : Base(++other) {}

    multivector_level_const_reverse_it(multivector_level_it<T> other) : Base(++other) {}
 protected:
    multivector_level_const_reverse_it(const BaseAll& b, const MultiVector_PositionT& mp, const multivector<T>* mv, int level)
       :  boost::iterator_adaptor<
             multivector_level_const_reverse_it<T>,
             multivector_level_const_it<T>
          >::iterator_adaptor_(base_type(b, mp, mv, level)) {}

    int my_level() const { return static_cast<int>(boost::prior(this->base().base())->first.size()) - 1; }
private:
    friend class boost::iterator_core_access;
    friend class multivector<T>;

    typename Base::super_t::reference dereference() const { return *boost::prior(this->base()); }

    void increment();
    void decrement();

    void advance(typename Base::super_t::difference_type n)
    {
      this->base_reference() += -n;
    }

    template <class OtherIterator>
    typename Base::super_t::difference_type
    distance_to(OtherIterator const& y) const
    {
      return this->base_reference() - y.base();
    }
};

template<typename T> 
class multivector_level_reverse_it : public multivector_level_const_reverse_it<T> {
 private:
    struct enabler {};  // a private type avoids misuse

 public:
    typedef multivector_level_const_reverse_it<T> Base;
    typedef typename multivector_const_it<T>::BaseAll BaseAll;

    multivector_level_reverse_it() : Base() {}

    multivector_level_reverse_it(int level) : Base(level) {}

    explicit multivector_level_reverse_it(BaseAll const& p) : Base(p) {}

    multivector_level_reverse_it(Base const& p) : Base(p) {}

    template <typename OtherValue>
    multivector_level_reverse_it(
        multivector_level_reverse_it<OtherValue> const& other
      , typename boost::enable_if<
            boost::is_convertible<OtherValue,Base>
          , enabler
        >::type = enabler()
    )
      : multivector_level_reverse_it(other) {}
 
    multivector_level_reverse_it(multivector_it<T>& other) : Base(other) {}
private:
    friend class multivector<T>;

    multivector_level_reverse_it(const BaseAll& b, const MultiVector_PositionT& mp, const multivector<T>* mv, int level)
        : Base(b, mp, mv, level) {}
};

template<typename T> 
    class multivector {
public:
    typedef MultiVector_PositionT position_type;
    typedef std::map<position_type, T> data_type;
    typedef T& reference;
    typedef T const& const_reference;
    typedef multivector_it<T> iterator;
    typedef multivector_const_it<T> const_iterator;
    typedef multivector_reverse_it<T> reverse_iterator;
    typedef multivector_const_reverse_it<T> const_reverse_iterator;
    typedef multivector_level_const_it<T> level_const_iterator;
    typedef multivector_level_it<T> level_iterator;
    typedef multivector_level_const_reverse_it<T> level_const_reverse_iterator;
    typedef multivector_level_reverse_it<T> level_reverse_iterator;
    typedef typename data_type::size_type size_type;
    typedef typename data_type::difference_type difference_type;
    typedef T value_type;
    typedef typename data_type::pointer pointer;
    typedef typename data_type::const_pointer const_pointer;

    explicit multivector() : m_data() {}
    explicit multivector(size_type n, const T& value= T()) : m_data() {
        for (size_type i = 0; i < n; ++i) {
            push_back(value);
        }
    }
    template <typename InputIterator>
    multivector(InputIterator first, InputIterator last) : m_data() {
    }
    multivector(const multivector<T>& x) {
    }
    
    ~multivector() {
        clear();
    }

    multivector<T>& operator=(const multivector<T>& x) {
        m_data = x.m_data;

        return *this;
    }

    iterator begin() {
        typename data_type::iterator it = m_data.begin();

        return iterator(it, it != m_data.end() ? it->first : MultiVector_PositionT(), this);
    }

    const_iterator begin() const {
        return const_cast<multivector*>(this)->begin();
    }

    level_iterator begin(const position_type& n) {
        typename data_type::iterator it = internal_begin(n);

        return level_iterator(it, it != m_data.end() ? it->first : MultiVector_PositionT(), this, static_cast<int>(n.size()));
    }

    level_const_iterator begin(const position_type& n) const {
        return const_cast<multivector*>(this)->begin(n);
    }

    iterator end() {
        typename data_type::iterator it = m_data.end();

        return iterator(it, MultiVector_PositionT(), this);
    }

    const_iterator end() const {
        return const_cast<multivector*>(this)->end();
    }

    level_iterator end(const position_type& n) {
        typename data_type::iterator it = internal_end(n);

        return level_iterator(it, n, this, static_cast<int>(n.size()));
    }

    level_const_iterator end(const position_type& n) const {
        return const_cast<multivector*>(this)->end(n);
    }

    reverse_iterator rbegin() {
        typename data_type::iterator it = m_data.rbegin().base();

        return reverse_iterator(it, MultiVector_PositionT(), this);
    }

    const_reverse_iterator rbegin() const {
        return const_cast<multivector*>(this)->rbegin();
    }

    level_reverse_iterator rbegin(const position_type& n) {
        typename data_type::iterator it = internal_end(n);

        return level_reverse_iterator(it, n, this, static_cast<int>(n.size()));
    }

    level_const_reverse_iterator rbegin(const position_type& n) const {
        return const_cast<multivector*>(this)->rbegin(n);
    }

    reverse_iterator rend() {
        return reverse_iterator(m_data.rend().base(), MultiVector_PositionT(), this);
    }

    const_reverse_iterator rend() const {
        return const_cast<multivector*>(this)->rend();
    }

    level_reverse_iterator rend(const position_type& n) {
        typename data_type::iterator it = internal_begin(n);

        return level_reverse_iterator(it, n, this, static_cast<int>(n.size()) - 1);
    }

    level_const_reverse_iterator rend(const position_type& n) const {
        return const_cast<multivector*>(this)->rend(n);
    }

    size_type size(const position_type& n = position_type()) const { 
        return m_data.size();
    }

    size_type max_size(const position_type& n = position_type()) const {
        return m_data.max_size();
    }
    //void resize(size_type sz, T c = T());  // It won't be supported
    //size_type capacity () const;
    bool empty(const position_type& n = position_type()) const {
        return m_data.empty();
    }
    //void reserve(size_type n);

    reference operator[](const position_type& n) {
        return m_data[n];
    }

    const_reference operator[](const position_type& n) const {
        return m_data[n];
    }
    //const_reference at(const position_type& n) const {
    //	return m_data[n];
    //}
    //reference at(const position_type& n) {
    //	return m_data[n];
    //}
    reference front(const position_type& n) {
        return m_data.front();
    }
    const_reference front(const position_type& n) const {
        return m_data.front();
    }
    reference back(const position_type& n) {
        return m_data.back();
    }
    const_reference back(const position_type& n) const {
        return m_data.back();
    }

    //void push_back(const T& x, const position_type& n = position_type()) {
    //}
    //void pop_back(const position_type& n = position_type()) {
    //}
    //iterator insert(iterator position, const T& x) {
    //	return iterator();
    //}
    //void insert(iterator position, size_type n, const T& x) {
    //}
    //template <class InputIterator>
    //void insert(iterator position, InputIterator first, InputIterator last) {
    //}
    void erase(iterator position) {
        if (position != end()) {
            typename data_type::iterator it = m_data.find(position->first);
            if (it != m_data.end()) {
                m_data.erase(it);
            }
        }
    }
    void erase(reverse_iterator position) {
        if (position != rend()) {
            typename data_type::iterator it = m_data.find(position->first);
            if (it != m_data.end()) {
                m_data.erase(it);
            }
        }
    }
    //iterator erase(iterator first, iterator last) {
    //	//m_data.erase(first, last);
    //	return iterator();
    //}
    void swap(multivector<T>& multivec) {
        m_data = multivec.m_data;
    }
    void clear(const position_type& n = position_type()) {
        m_data.clear();
    }
private:
    data_type m_data;

    typename data_type::iterator internal_end(position_type const& n) {
        typename data_type::iterator it;

        position_type n2(n);
        while (n2.size()) {
            ++n2[n2.size() - 1];  // Address of the next element in the previous level
            if ((it = m_data.find(n2)) != m_data.end()) {
                break;
            }
            n2.pop_back();
        } 
        if (!n2.size()) {
            it = m_data.rbegin().base();
        }

        return it;
    }

    typename data_type::iterator internal_begin(position_type const& n) {
        position_type n2(n);
        n2.push_back(0);  // Address of the level first element 
        typename data_type::iterator it = m_data.find(n2);
        if (it == m_data.end()) { // If not find element, points to the end of level
            it = internal_end(n);
        }

        return it;
    }
};

template<typename T> 
void multivector_const_it<T>::increment() { 
  if (m_mv && static_cast<typename multivector<T>::const_iterator>(this->base_reference()) != m_mv->end()) {
    ++this->base_reference();
  }
}

template<typename T> 
void multivector_const_it<T>::decrement() { 
  if (m_mv && static_cast<typename multivector<T>::const_iterator>(this->base_reference()) != m_mv->begin()) {
    --this->base_reference();
  }
}

template<typename T> 
void multivector_level_const_it<T>::increment() { 
  if (this->base().m_mv && static_cast<typename multivector<T>::const_iterator>(this->base_reference()) != this->base().m_mv->end()) {
    do {
        ++this->base_reference();
    } while (static_cast<typename multivector<T>::const_iterator>(this->base_reference()) != this->base().m_mv->end() && my_level() > m_level); //base().m_mp->size());
  }
}

template<typename T> 
void multivector_level_const_it<T>::decrement() { 
  if (this->base().m_mv && static_cast<typename multivector<T>::const_iterator>(this->base_reference()) != this->base().m_mv->begin()) {
    do {
        --this->base_reference();
    } while (static_cast<typename multivector<T>::const_iterator>(this->base_reference()) != this->base().m_mv->begin() && my_level() > m_level && // base().m_mp->size() &&
            this->base().m_mp->size()  // Test the exceptional case when it points to end (in this case, m_mp->size() is equal 0) and only one iteration is enough
            );
  }
}

template<typename T> 
void multivector_level_const_reverse_it<T>::increment() { 
  multivector_const_it<T> const& mvcit = this->base().base();
  if (mvcit.m_mv && static_cast<typename multivector<T>::const_iterator>(this->base_reference().base().base()) != mvcit.m_mv->begin()) {
    do {
        --this->base_reference();
    } while (static_cast<typename multivector<T>::const_iterator>(this->base_reference().base().base()) != mvcit.m_mv->begin() && my_level() > this->base().m_level);
  }
}

template<typename T> 
void multivector_level_const_reverse_it<T>::decrement() { 
  multivector_const_it<T> const& mvcit = this->base().base();
  if (mvcit.m_mv && static_cast<typename multivector<T>::const_iterator>(this->base_reference().base().base()) != mvcit.m_mv->end()) {
    do {
        ++this->base_reference();
    } while (static_cast<typename multivector<T>::const_iterator>(this->base_reference().base().base()) != mvcit.m_mv->end() && my_level() > this->base().m_level); 
  }
}
}} // namespace cnome { namespace actions {

#endif // MULTIVECTOR_H

